package org.jspar.tile;

import java.util.ArrayList;
import java.util.List;


public class Tile {

	private static final int LEFT = 0;
	private static final int RIGHT = 1;
	private static final int TOP = 2;
	private static final int BOTTOM = 3;
	
	private Tile lb, bl, tr, rt;
	private int x, y;
	private int width, height;
	private ITileContent content;
	private int id;
	private ITileDelegate delegate = DefaultTileDelegate.INSTANCE;

	private static int number = 0;

	public Tile(int x, int y, int width, int height, ITileDelegate delegate) {
		this(x, y, width, height, null, delegate);
	}
	
	public Tile(int x, int y, int width, int height, ITileContent c, ITileDelegate delegate) {
		this.x = x;
		this.y = y;
		this.width = width;
		this.height = height;
		this.content = c;
		this.delegate = delegate;
		this.id = number++;
	}
	public ITileContent content() { return content; }
	public void setContent(ITileContent content) { this.content = content; }
	public int id() { return id; }
	public int x() { return x; }
	public int y() { return y; }
	public int width() { return width; }
	public int height() { return height; }
	public int left() { return x; }
	public int right() { return x + width; }
	public int top() { return y; }
	public int bottom() { return y + height; }

	public Tile leftBottom() { return lb; }
	public Tile bottomLeft() { return bl; }
	public Tile topRight() { return tr; }
	public Tile rightTop() { return rt; }

	public boolean isSpace() { return content == null; }
	
	public boolean isSolid() {
		return delegate.isSolid(this);
	}
	
	public Tile locate(int px, int py) {
		Tile res = this;

		if (py < y || py == y && lb != null)
			res = lb != null ? lb.locate(px, py) : null;
	    else if (bottom() < py)
	    	res = rt != null ? rt.locate(px, py) : null;

	    if (res == null)
	    	return null;
	    if (res.x > px || res.x == px && res.bl != null)
	    	return res.bl != null ? res.bl.locate(px, py) : null;
	    if (res.right() < px)
	    	return res.tr != null ? res.tr.locate(px, py) : null;
	    return res;
	}

	public boolean enclosePoint(int px, int py) {
		return left() <= px && px < right()
				&& top() <= py && py < bottom();
	}

	public boolean containsPoint(int px, int py) {
		return left() <= px && px <= right()
				&& top() <= py && py <= bottom();
	}

	/*public Tile nextTileRight(int y) {
		Tile res = topRight();
		while (res.bottom() < y)
			res = res.leftBottom();
		return res;
	}
	
	public Tile nextTileUp(int x) {
		Tile res = rightTop();
		while (res.left() > x)
			res = res.bottomLeft();
		return res;
	}

	public Tile nextTileLeft(int y) {
		Tile res = bottomLeft();
		while (res.top() <= y)
			res = res.rightTop();
		return res;
	}

	public Tile nextTileDown(int x) {
		Tile res = leftBottom();
		while (res.right() <= x)
			res = res.topRight();
		return res;
	}*/

	/**
	 * @Return the right tile from the split
	 */
	public Tile splitX(int px) {
		Tile t;
		Tile res = new Tile(px, y, -1, -1, content, delegate);

		res.bl = this;
		res.tr = tr;
		res.rt = rt;

		// Adjust along right edge
		for (t = tr; t.bl == this; t = t.lb)
			t.bl = res;
		tr = res;

		// Adjust along top edge
		for (t = rt; t.left() >= px; t = t.bl)
			t.lb = res;
		rt = t;

		// Adjust along bottom edge
		t = lb;
		while(t.right() <= px) t = t.tr;
		res.lb = t;
		while(t.rt == this) {
			t.rt = res;
			t = t.tr;
		}
		return res;
	}

	/**
	 * @Return the top tile from the split
	 */
	public Tile splitY(int py) {
		Tile t;
		Tile res = new Tile(x, y, -1, -1, content, delegate);
		res.lb = this;
		res.rt = rt;
		res.tr = tr;

		// set our new horizontal position
		y = py;

		// Adjust along top edge
		for (t = rt; t.lb == this; t = t.bl)
			t.lb = res;
		rt = res;

		// Adjust along right edge
		for (t = tr; t.bottom() <= py; t = t.lb)
			t.bl = res;
		tr = t;

		// Adjust along left edge
		t = bl;
		while(t.top() >= py)
			t = t.rt;
		res.bl = t;
		while(t.tr == this) {
			t.tr = res;
			t = t.rt;
		}
		return res;
	}

	public void joinX(Tile tile) {
		Tile t;

		// adjust along top
		for (t = tile.rt; t.lb == tile; t = t.bl)
			t.lb = this; 

		// adjust along bottom
		for (t = tile.lb; t.rt == tile; t = t.tr)
			t.rt = this; 

		// adjust along shared side
		if (left() < tile.left()) {
			for (t = tile.tr; t.bl == tile; t = t.lb)
				t.bl = this; 
			tr = tile.tr;
			rt = tile.rt;
		} else {
			for (t = tile.bl; t.tr == tile; t = t.rt)
				t.tr = this; 
			bl = tile.bl;
			lb = tile.lb;
			x = tile.x;
		}
	}

	/** Join verticaly, destroying tile
	 */
	public void joinY(Tile tile) {
		Tile t;

		// adjust along right
		for (t = tile.tr; t.bl == tile; t = t.lb)
			t.bl = this; 

		// adjust along left
		for (t = tile.bl; t.tr == tile; t = t.rt)
			t.tr = this; 

		// adjust along shared side
		if (bottom() > tile.bottom()) {
			for (t = tile.rt; t.lb == tile; t = t.bl)
				t.lb = this; 
			rt = tile.rt;
			tr = tile.tr;
			y = tile.y;
		} else {
			for (t = tile.lb; t.rt == tile; t = t.tr)
				t.rt = this; 
			lb = tile.lb;
			bl = tile.bl;
		}
	}
	
	public Tile locate(Position p) {
		Tile t = this;

		if (t == null)
			return null;

		// first find the right 'row' of tiles
		if (p.y() < t.y || p.y() == t.y && t.lb != null) {
			t = t.lb != null ? t.lb.locate(p) : null;
		} else if ((t.height + t.y) < p.y()) {
			t = t.rt != null ? t.rt.locate(p) : null;
		}
		if (t == null)
			return null; // bad requests cause big problems

		// walk down the 'row'
		if (t.x > p.x() || t.x == p.x() && t.bl != null)
			return t.bl != null ? t.bl.locate(p) : null;
		if ((t.width + t.x) < p.x())
			return t.tr != null ? t.tr.locate(p) : null;
		return t;
	}

	public String toString() {
		return id + " <"+left()+" "+top()+" "+right()+" "+bottom()+">" + (content != null ? content.toString() : "");
	}
	
	public Tile insertTile(int xorg, int yorg, int xsize, int ysize,
			ITileContent what) {
		Tile newTile = null;

		int x = xorg + xsize;
		int y = yorg + ysize;
		int ymark = y;

		/* First see if such a tile can be made: */
		if (areaSearch(xorg, yorg, xsize, ysize) != null)
			return null;

		/* locate the top left-hand (LH) corner tile for the AOI */
		Tile top = locate(xorg + 1, y);

		/*
		 * Now split this tile vertically, as necessary: <leftBot> becomes the
		 * lower tile
		 */
		Tile leftBot = top.vsplit(y); /* <leftBot> becomes the lower tile */

		/* Do the same to the bottom of the AOI: */
		Tile temp = top.locate(xorg, yorg);
		Tile bot = temp.vsplit(yorg);

		/*
		 * Now begin a loop, splitting tiles as you go. Note that the pointers
		 * for, and the size of <new_> changes as you go along to insure
		 * correctness.
		 */
		Tile left = leftBot;
		Tile right = null;

		while (ymark > yorg) {
			newTile = left.hsplit(xorg);
			right = newTile.hsplit(x);

			delegate.insertContents(newTile, what);
			left.vmerge();
			right.vmerge();
			newTile.vmerge();

			ymark = newTile.y;
			left = newTile.locate(xorg, ymark);
			if (left != null && left.y >= ymark)
				left = newTile.locate(xorg, ymark - 1);
			if (left != null && (left.x + left.width) <= xorg) {
				if (newTile.lb.height == 1)
					left = newTile.locate(xorg + 1, ymark);
				else
					left = newTile.locate(xorg + 1, ymark - 1);
			}
		}
		/* Cleanup the tiles directly below the area of interest: */
		if (newTile.bl != null && newTile.bl.lb != null)
			newTile.bl.lb.vmerge();
		if (right != null && right.lb != null)
			right.lb.vmerge();

		/*if (!new_.verify_tile_space()) {
			System.err.println("insert_tile: Corrupted tile space! abort! (on exit)");
			return null;
		}*/
		return newTile;
	}
	
	private Tile vmerge() {
		Tile t = this;
		Tile temp;

		/* If there's a guy on top */
		/*
		 * And things line up OK
		 */
		if (t.rt != null && delegate.isContentEquivalent(t, t.rt)
				&& t.rt.x == t.x && t.rt.width == t.width) {
			temp = t.rt; /* nuke the guy on top */

			/* Fixup the tile contents to reflect these changes: */

			t.height += temp.height;
			t.rt = temp.rt;
			t.tr = temp.tr;

			/*
			 * need to fix all of the pointers pointing to <temp> so they will
			 * point to <t>
			 */

			List<Tile> scrap = temp.listNeighbors(LEFT);
			for (Tile tt : scrap) {
				if (tt.tr == temp)
					tt.tr = t;
			}

			scrap = temp.listNeighbors(RIGHT);
			for (Tile tt : scrap) {
				if (tt.bl == temp)
					tt.bl = t;
			}

			scrap = temp.listNeighbors(TOP);
			for (Tile tt : scrap) {
				if (tt.lb == temp)
					tt.lb = t;
			}
			delegate.manageContentsVmerge(t, temp);
			delegate.manageContentsDeadTile(temp);
			temp = null;
		}
		return t;
	}
	
	private Tile hsplit(int xs) {
		if (xs > x && xs < (x + width)) {
			Tile c = copy();
			c.bl = this;
			c.width = x + width - xs;
			c.x = xs;
			tr = c;

			width = xs - x;
			c.lb = locate(xs + 1, c.y);

			/*
			 * Now hunt down all of the special cases where the <= vs < issues
			 * can bite you: (These work around weaknesses in the definition of
			 * a tile as being inclusive vs being exclusive of its borders)
			 */
			if (c.lb != null && c.lb.x > c.x)
				c.lb = locate(xs, c.y);
			rt = locate(xs - 1, y + height + 1);
			if (rt != null && (rt.x + rt.width) <= xs)
				rt = locate(xs, y + height + 1);
			cleanupNeighbors();
			c.cleanupNeighbors();

			// if (!verify_tile_space() || !c.verify_tile_space())
			// {
			// System.err.println("hsplit_tile: Corrupted tile space!");
			// }

			/* Clean up the contents of these tiles: */
			delegate.manageContentsHsplit(this, c);
			return (c);
		}
		if (xs == x)
			return this;
		if (xs == (x + width))
			return tr;
		return null;
	}
	
	private Tile vsplit(int ys) {
		if (ys > y && ys < (y + height)) {
			Tile c = copy(); /* <c> becomes the lower tile */
			lb = c;
			height = y + height - ys;
			y = ys;

			c.rt = this;
			c.height = ys - c.y;
			c.tr = locate(c.x + c.width + 1, c.y + c.height + 1);
			if (c.tr != null && c.tr.y >= y)
				c.tr = locate(c.x + c.width + 1, c.y + c.height);

			bl = locate(x - 1, ys);

			/*
			 * Now hunt down all of the special cases where the <= vs < issues
			 * can bite you: (These work around weaknesses in the definition of
			 * a tile as being inclusive vs being exclusive of its borders)
			 */
			if (bl != null && (bl.y + bl.height) <= ys)
				bl = locate(x - 1, ys + 1);
			if (bl != null && (bl.y > y))
				bl = locate(x - 1, ys - 1);
			if (bl != null && (bl.x + bl.width) < x)
				bl = locate(x, ys);

			cleanupNeighbors();
			c.cleanupNeighbors();

			//if (!verify_tile_space() || !c.verify_tile_space()) {
			//	System.err.println("vsplit_tile: Corrupted tile space!");
			//}
			/* Clean up the contents of these tiles: */
			delegate.manageContentsVsplit(this, c);
			return c;
		}
		if (ys == y)
			return lb;
		
		if (ys == (y + height))
			return this;
		
		return null;
	}
	
	private void cleanupNeighbors() {
		List<Tile> temp = listNeighbors(LEFT);
		for (Tile t : temp) {
			if ((t.y + t.height) <= (y + height) && t != this)
				t.tr = this;
		}

		temp = listNeighbors(RIGHT);
		for (Tile t : temp) {
			if (t.y >= y && t != this)
				t.bl = this;
		}

		temp = listNeighbors(TOP);
		for (Tile t : temp) {
			if (t.x >= x && t != this)
				t.lb = this;
		}

		temp = listNeighbors(BOTTOM);
		for (Tile t : temp) {
			if ((t.x + t.width) <= (x + width) && t != this)
				t.rt = this;
		}
	}
	
	private List<Tile> listNeighbors(int side) {
		List<Tile> tlist = new ArrayList<Tile>();
		Tile s;

		switch (side) {
		case TOP:
			s = rt;
			if (s != null) {
				tlist.add(0, s);
				s = s.bl;
				while (s != null && s.x >= x) {
					tlist.add(0, s);
					s = s.bl;
				}
			}
			break;

		case RIGHT:
			s = tr;
			if (s != null) {
				tlist.add(s);
				s = s.lb;
				while (s != null && s.y >= y) {
					tlist.add(s);
					s = s.lb;
				}
			}
			break;

		case BOTTOM:
			s = lb;
			if (s != null) {
				tlist.add(s);
				s = s.tr;
				while (s != null && s.x < (x + width)) {
					tlist.add(s);
					s = s.tr;
				}
			}
			break;

		case (LEFT):
			s = bl;
			if (s != null) {
				tlist.add(0, s);
				s = s.rt;
				while (s != null && s.y < (y + height)) {
					tlist.add(0, s);
					s = s.rt;
				}
			}
			break;
		}
		return tlist;
	}
	
	private Tile copy() {
		Tile s = new Tile(x, y, width, height, content, delegate);
		s.bl = bl;
		s.lb = lb;
		s.rt = rt;
		s.tr = tr;
		return s;
	}
	public Tile areaSearch(int xorg, int yorg, int xsize, int ysize) {
		int x = xorg + xsize;
		Tile s = locate(xorg, yorg + ysize);
		
		/* Boundry condition problem */
		if ((s.x + s.width) <= xorg && s.tr != null)
			s = s.tr.locate(xorg + 1, yorg + ysize);

		if (s.isSolid())
			return s;

		if ((s.x + s.width) < x)
			return s.tr;
		if (s.y > yorg)
			return s.areaSearch(xorg, yorg, xsize, s.y - yorg);
		return null;
	}

	public Tile bestTileInSpace(ITileComparator comparator) {
		 List<Tile> tl = nonFreespace();
		 Tile temp = tl.get(0);

		 for (int i = 1; i < tl.size(); ++i) {
			 temp = comparator.compare(temp, tl.get(i)) ? temp : tl.get(i);
		 }
		 return temp;
	}

	public List<Tile> nonFreespace() {
		return enumerate(new ArrayList<Tile>(), new UsedSpacePredicate());
	}
	
	public List<Tile> allspace() {
		return enumerate(new ArrayList<Tile>(), new TruePredicate());
	}

	public List<Tile> enumerate(List<Tile> soFar, ITilePredicate predicate) {
		Tile temp = find_ULHC();
	    while (temp != null) {
	    	soFar = temp.helpEnumerate(soFar, predicate);
	    	temp = temp.leftBottom();
	    }
	    return soFar;
	}
	
	private List<Tile> helpEnumerate(List<Tile> soFar, ITilePredicate predicate) {
		/* Add the given tile to the listing: */
		if (predicate.test(this))
			soFar.add(this);

		if (tr != null) {
			/* Enmumerate all of the tiles on the right-side of the given tile: */
			for (Tile temp : listNeighbors(RIGHT)) {
				if (temp.bl == this)
					temp.helpEnumerate(soFar, predicate);
			}
		}
		return soFar;
	}
	
	public Tile find_ULHC() {
		Tile temp = this;

		/* find the upper-left-hand corner of the given tile-set */
		if (temp.bl == null && temp.rt == null)
			return (temp);

		/* Walk up to the proper 'row': */
		while (temp.rt != null)
			temp = temp.rt;

		/* Walk over to the proper 'column': */
		while (temp.bl != null)
			temp = temp.bl;

		return temp.find_ULHC();
	}

	public Tile find_LRHC() {
		Tile temp = this;

		/* find the lower-right-hand corner of the given tile-set */
		if (temp.lb == null && temp.tr == null)
			return temp;

		/* Walk up to the proper 'row': */
		while (temp.lb != null)
			temp = temp.lb;

		/* Walk over to the proper 'column': */
		while (temp.tr != null)
			temp = temp.tr;

		return temp.find_LRHC();
	}

	public static void translateOrigin(List<Tile> tiles, int x, int y) {
		for (Tile t : tiles) {
			t.x += x;
			t.y += y;
		}
	}

	public List<Tile> areaEnumerate(ITilePredicate predicate, int xorg,
			int yorg, int xext, int yext) {
		int maxX = xorg + xext;
		int maxY = yorg + yext;

		Tile temp = locate(xorg, maxY);
		ArrayList<Tile> soFar = new ArrayList<Tile>();
		while (temp != null && (temp.y() >= yorg || temp.bottom() > yorg)) {
			temp.helpAreaEnumerate(soFar, predicate,
					xorg, yorg, maxX, maxY);
			temp = temp.lb == null ? null : temp.lb.locate(xorg, temp.y());
		}
		return soFar;
	}

	private void helpAreaEnumerate(ArrayList<Tile> soFar,
			ITilePredicate predicate, int xorg, int yorg, int maxX, int maxY) {
		int x = right();
		int y = bottom();

		if (predicate.test(this)
				&& (((x <= maxX && x > xorg)
						|| (x() < maxX && x() >= xorg)
						|| (x >= maxX && x() <= xorg))
				&& ((y <= maxY && y > yorg)
						|| (y() < maxY && y() >= yorg)
						|| (y >= maxY && y() <= yorg)))) {
			soFar.add(this);
		}

		if (tr != null) {
			for (Tile t : listNeighbors(RIGHT)) {
				if (t.x() >= maxX)
					break;
				if (t.bl == t)
					t.helpAreaEnumerate(soFar, predicate, xorg, yorg, maxX, maxY);
			}
		}
	}

	public Rectangle getBounds() {
		return new Rectangle(x, y, width, height);
	}
	
}
